// Author: Domien Nowicki

#ifndef MAPBACKTRACK_H
#define MAPBACKTRACK_H

#include "MapSolver.h"
#include <stack>

class MapBacktrack: public MapSolver
{
public:

	// Constructors
	MapBacktrack(const Map& map, const Properties& properties);

	// Destructor
	virtual ~MapBacktrack();

	// Next move from backtracking algorithm
	virtual Move NextMove();
	// Initialization for starting backtracking
	virtual void Initialize();
	// Get hint
	virtual Move HintMove();

private:
	// Helper structure for bookkeeping the history of coloring the provinces
	struct HistoryStep
	{
		unsigned int tested;
		int nexttry;
		Land* land;
		Province* province;
	};

	// Helper functions
	bool CanColor(Province *province, Color *availableColor);
	bool UndoDoubles(Move *move);
	bool FillMove(Move *move);
	void ClearHistory();
	unsigned int ColorToIndex(const Color& color);
	Color IndexToColor(const unsigned int index);
	void DoMove(const Move* move);
	int FindUntestedIndex(unsigned int previousTested, Province *emptyProvince);
	void PushInitialHistory(const Color& color, Land* land, Province* province);
	bool FinishLastMove(Move *move);
	void NextTest(int index);
	int NextUntestedIndex();
	void PopHistoryStep();
	void EraseMove(Move *move);
	bool MismatchMove(bool eraseFirst, Move *move);
	Color EraseColored(const Color& orgColor, const Color& newColor);

	// Bookkeeping stack 
	std::stack<HistoryStep> history;

	// Original map to solve
	const Map* originalMap;
};

#endif //MAPBACKTRACK_H